package stmo.树.二叉树;

import stmo.队列.Queue;

/**
 *  二叉查找树
 */

public class BinaryTree<Key extends Comparable<Key>,Value>{

    //记录根结点
    private Node root;

    //记录树中元素的个数
    private int N;

    //成员内部类
    private class Node {
        //存储键
        private Key key;
        //存储值
        private Value value;
        //记录左结点
        private Node left;
        //记录右结点
        private Node right;
        //构造方法
        public Node(Key key,Value value,Node left,Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    //获取树中元素的个数
    public int size() {
        return  N;
    }

    //向树中添加元素key-value
    public void put(Key key,Value value) {
        root = put(root, key, value);
    }

    //向指定的树x中添加key-value，并返回添加元素后的新树
    public Node put(Node x,Key key,Value value) {

        //如果x子树为空
        if (x == null) {
            //元素个数+1
            N++;
            return new Node(key,value,null,null);
        }

        // 如果x子树不为空，则比较x结点的键和key的大小：
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            // 如果key小于x结点的键，则继续找x结点的左子树
            x.left = put(x.left,key,value);
        }else if (cmp > 0) {
            // 如果key大于x结点的键，则继续找x结点的右子树
            x.right = put(x.right,key,value);
        }else {
            // 如果key等于x结点的键，则替换x结点的值为value
            x.value = value;
        }
        return x;
    }

    //查询树中指定key对应的value
    public Value get(Key key) {
        return get(root,key);
    }

    //从指定的树x中，查找key对应的值
    public Value get(Node x,Key key) {
        //如果x树为null
        if (x == null) {
            return null;
        }
        //如果x树不为null，则比较x结点的键和key的大小：
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            // 如果key小于x结点的键，则继续找x结点的左子树
            return get(x.left, key);
        }else if (cmp > 0) {
            // 如果key大于x结点的键，则继续找x结点的右子树
            return get(x.right,key);
        }else {
            // 如果key等于x结点的键，则找到了键为key的结点，返回value即可
            return x.value;
        }
    }

    //删除树中key对应的value
    public void delete(Key key) {
        delete(root,key);
    }

    //删除指定树x中key对应的value，并返回删除后的新树
    public Node delete(Node x,Key key) {
        //x树为null
        if (x == null) {
            return null;
        }
        //如果x树不为null，则比较x结点的键和key的大小：
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            // 如果key小于x结点的键，则继续找x结点的左子树
            x.left = delete(x.left,key);
        }else if (cmp > 0) {
            // 如果key大于x结点的键，则继续找x结点的右子树
            x.right = delete(x.right,key);
        }else {
            // 如果key等于x结点的键，则找到了键为key的结点，完成删除结点，要删除的结点就是x

            //让元素个数-1
            N--;

            //得找到右子树中最小的结点
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            Node minNode = x.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            //删除右子树中最小的结点
            Node n = x.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                }else {
                    n = n.left;
                }
            }
            //让x结点的左子树成为minNode的左子树
            minNode.left = x.left;
            //让x结点的右子树成为minNode的右子树
            minNode.right = x.right;
            //让x结点的父结点指向minNode
            x = minNode;
        }
        return x;
    }

    //查找整个树中最小的键
    public Key min() {
        return min(root).key;
    }

    //在指定树x中找出最小键所在的结点
    public Node min(Node x) {
        //需要判断x还有没有左子结点，如果有继续向左找，如果没有则x就是最小键所在的结点
        if (x.left != null) {
            return min(x.left);
        }else {
            return x;
        }
    }

    //查找整个树中最大的键
    public Key max() {
        return max(root).key;
    }

    //在指定树x中找出最大键所在的结点
    public Node max(Node x) {
        //需要判断x还有没有右子结点，如果有继续向右找，如果没有则x就是最小键所在的结点
        if (x.right != null) {
            return max(x.right);
        }else {
            return x;
        }
    }

    //前序遍历键
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root,keys);
        return keys;
    }

    //获取指定树x的所有键，并放到keys队列中
    public void preErgodic(Node x,Queue<Key> keys) {
        if (x == null) {
            return;
        }
        //把x结点的key放入到keys中
        keys.enqueue(x.key);

        //递归遍历x结点的左子树
        if (x.left != null) {
            preErgodic(x.left,keys);
        }
        //递归遍历x结点的右子树
        if (x.right != null) {
            preErgodic(x.right,keys);
        }
    }

    //使用中序遍历获取树中所有键
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root,keys);
        return keys;
    }

    //使用中序遍历获取指定树x中所有的键，并存放到key中
    public void midErgodic(Node x,Queue<Key> keys) {

        if (x == null) {
            return;
        }
        //先递归把左子树中的键放到keys中
        if (x.left != null) {
            midErgodic(x.left,keys);
        }
        //把当前结点x的键放到keys中
        keys.enqueue(x.key);
        //再递归把右子树中的键放到keys中
        if (x.right != null) {
            midErgodic(x.right,keys);
        }
    }


    //使用后序遍历获取树中所有键
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root,keys);
        return keys;
    }

    //使用后序遍历获取指定树x中所有的键，并存放到key中
    public void afterErgodic(Node x,Queue<Key> keys) {
        if (x == null) {
            return;
        }
        //先递归把右子树中的键放到keys中
        if (x.left != null) {
            afterErgodic(x.left,keys);
        }

        //再递归把左子树中的键放到keys中
        if (x.right != null) {
            afterErgodic(x.right,keys);
        }

        //把当前结点x的键放到keys中
        keys.enqueue(x.key);
    }


    //使用层序遍历获取树中所有键
    public Queue<Key> layerErgodic() {

        //创建队列，存储每一层的结点
        Queue<Key> keys = new Queue<>();

        if (root == null) {
            return keys;
        }

        Queue<Node> nodes = new Queue<>();

        nodes.enqueue(root);

        while (!nodes.isEmpty()) {
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //如果当前结点的左子结点不为空，则把左子结点放入到队列中，
            if (n.left != null) {
                nodes.enqueue(n.left);
            }
            //如果当前结点的右子结点不为空，则把右子结点放入到队列中
            if (n.right != null) {
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }

    //获取整个树的最大深度
    public int maxDepth() {
        return maxDepth(root);
    }

    //获取指定树x的最大深度
    public int maxDepth(Node x) {
        if (x == null) {
            return 0;
        }
        //x的最大深度
        int max = 0;
        //左子树的最大深度
        int maxL = 0;
        //右子树的最大深度
        int maxR = 0;

        //计算x结点左子树的最大深度
        if (x.left != null) {
            maxL = maxDepth(x.left);
        }
        //计算x结点右子树的最大深度
        if (x.right != null) {
            maxR = maxDepth(x.right);
        }
        //比较左子树最大深度和右子树最大深度，取较大值+1即可
        max = maxL>maxR?maxL+1:maxR+1;
        return max;
    }
}
